class Solution {
public:

    int dx[4] = { 0, 0, 1, -1 };
    int dy[4] = { 1, -1, 0, 0 };
    int row, col;

    void solve(vector<vector<char>>& image) {
        row = image.size();
        col = image[0].size();
        for (int i = 0; i < row; i++)
            for (int j = 0; j < col; j++)
                if (!(i != 0 && i != row - 1 && j != 0 && j != col - 1) && image[i][j] == 'O')
                    dfs(image, i, j);
        for (int i = 0; i < row; i++)
            for (int j = 0; j < col; j++)
                if (image[i][j] == '.')
                    image[i][j] = 'O';
                else if (image[i][j] == 'O')
                    image[i][j] = 'X';
    }

    void dfs(vector<vector<char>>& image, int sr, int sc)
    {
        image[sr][sc] = '.';
        for (int i = 0; i < 4; i++)
        {
            int x = sr + dx[i];
            int y = sc + dy[i];
            if (x >= 0 && x < row && y >= 0 && y < col && image[x][y] == 'O')
                dfs(image, x, y);
        }
    }
};
class Solution {
public:

    int dx[4] = { 0, 0, 1, -1 };
    int dy[4] = { 1, -1, 0, 0 };
    int row, col;
    vector<vector<int>> ret;
    vector<vector<int>> pacificAtlantic(vector<vector<int>>& image) {
        row = image.size();
        col = image[0].size();
        vector<vector<bool>> flagA(row, vector<bool>(col));
        vector<vector<bool>> flagP(row, vector<bool>(col));

        for (int i = 0; i < row; i++)
            for (int j = 0; j < col; j++)
            {
                if (!(i != 0 && j != 0))
                    dfs(image, i, j, flagP);
                if (!(i != row - 1 && j != col - 1))
                    dfs(image, i, j, flagA);
            }

        for (int i = 0; i < row; i++)
            for (int j = 0; j < col; j++)
                if (flagA[i][j] == true && flagP[i][j] == true)
                    ret.push_back({ i, j });

        return ret;
    }

    void dfs(vector<vector<int>>& image, int sr, int sc, vector<vector<bool>>& flag)
    {
        flag[sr][sc] = true;
        int num = image[sr][sc];
        for (int i = 0; i < 4; i++)
        {
            int x = sr + dx[i];
            int y = sc + dy[i];
            if (x >= 0 && x < row && y >= 0 && y < col && image[x][y] >= num && flag[x][y] == false)
                dfs(image, x, y, flag);
        }
    }
};
class Solution {
public:
    vector<vector<char>> updateBoard(vector<vector<char>>& board, vector<int>& click) {
        if (board[click[0]][click[1]] == 'M')
        {
            board[click[0]][click[1]] = 'X';
            return board;
        }
        row = board.size();
        col = board[0].size();
        dfs(board, click);
        return board;
    }
    int dx[8] = { 0, 0, 1, -1, 1, 1, -1, -1 };
    int dy[8] = { 1, -1, 0, 0, 1, -1, 1, -1 };
    int row, col;

    void dfs(vector<vector<char>>& board, vector<int>& click)
    {
        int sr = click[0];
        int sc = click[1];

        int count = 0;
        for (int i = 0; i < 8; i++)
        {
            int x = sr + dx[i];
            int y = sc + dy[i];
            if (x >= 0 && x < row && y >= 0 && y < col && board[x][y] == 'M') count++;
        }
        if (count)
        {
            board[sr][sc] = count + '0';
            return;
        }
        else
        {
            board[sr][sc] = 'B';
            for (int i = 0; i < 8; i++)
            {
                int x = sr + dx[i];
                int y = sc + dy[i];
                vector<int> v{ x, y };
                if (x >= 0 && x < row && y >= 0 && y < col && board[x][y] == 'E')
                    dfs(board, v);
            }
        }
    }
};
class Solution {
public:
    int dx[2] = { 1, 0 };
    int dy[2] = { 0, 1 };
    int ret = 0;
    bool flag[100][100];
    int wardrobeFinishing(int m, int n, int cnt) {
        dfs(m, n, cnt, 0, 0);
        return ret;
    }
    void dfs(int m, int n, int cnt, int a, int b)
    {
        flag[a][b] = true;
        ret++;
        for (int k = 0; k < 2; k++)
        {
            int x = a + dx[k];
            int y = b + dy[k];
            int i = x, j = y;
            int count = 0;
            while (x)
            {
                count += x % 10;
                x /= 10;
            }
            while (y)
            {
                count += y % 10;
                y /= 10;
            }
            if (i >= 0 && i < m && j >= 0 && j < n && count <= cnt && flag[i][j] == false)
            {
                flag[i][j] = true;
                dfs(m, n, cnt, i, j);
            }
        }
    }
};
